The problem of program obfuscation is to transform the code of a program so as to make it essentially “unintelligible” while still preserving its functionality. In other words, given an obfuscated program, an attacker should be able to do no more than observe its input output behavior. Such a requirement is most naturally formalized using a “virtual black box” definition: anything that can be efficiently computed given the obfuscated program can also be efficiently computed given only oracle access to the program.
Program obfuscation is a problem of fundamental importance. An obfuscated program is like a trusted party; you can execute it to perform tasks that it is intended for, however, it will refuse to do anything else (with the secrets it has). While the most obvious application of program obfuscation is for various forms of software production, given a program obfuscation scheme (and some basic primitives like a symmetric key encryption scheme), it is also possible to design a whole array of advanced cryptography primitives. Among the primitives, which can be constructed using program obfuscation are: public key encryption, identity based encryption, attribute based and predicated based encryption, etc. In addition, an obfuscation scheme (under the most natural virtual black box definition) would allow one to remove random oracles from various cryptography constructions to obtain constructions secure in the standard model.
While various heuristic techniques to obfuscate programs exist, their main results are disappointingly negative. In particular, it was shown that program obfuscation under the virtual black box definition (and some of its natural variants) is impossible. In particular, a family of unobfuscatable functions was exhibited where any source code implementing the function gives the attacker a significant advantage over if he only had oracle access to the function. Subsequently, a somewhat stronger definition was considered and impossibility results were significantly expanded to cover a large class of functionalities. In sharp contrast to these negative results, positive results on obfuscation have been relatively rare and known only for very specific functionalities.